package com.mxw.算法之美.a12搜索;

import com.mxw.算法之美.a11图.a01Graph;
import sun.misc.Queue;

import javax.management.Query;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author Administrator
 * @create 2024/7/31 14:40
 */
public class a01广度搜索BFS {

    /**
     * 地毯式层层推进的搜索
     *
     * 时间复杂度0(n)
     */


    /**
     * 寻找从s到t的最短路径
     */

    a01Graph graph = new a01Graph(10);


    public void bfs(int s, int t) {
        if (s == t) return;

        int v = graph.getV();
        LinkedList<Integer>[] adj = graph.getAdj();
        // 备忘录
        boolean[] visited = new boolean[v];
        visited[s] = true;

        // 已经被访问，但相连的顶点没有被访问的顶点
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(s);

        // 记录搜索路径 通过顶点2的邻接表访问到顶点3，prev[3] = 2
        int[] prev = new int[v];
        Arrays.fill(prev, -1);

        while (!queue.isEmpty()) {
            int w = queue.poll();
            // adj[w] 连接了几个节点
            for (int i = 0; i < adj[w].size(); i++) {
                int q = adj[w].get(i);
                // q没有被访问
                if (!visited[q]) {
                    prev[q] = w;
                    if (q == t){
                        // 找到T
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }
}
